package sortingBasic.insertionSort;

/**
 * 插入排序
 * mxf
 * 2018年5月18日17:09:23
 */
public class InsertionSort {

    private InsertionSort(){}
    public static void sort(Comparable[] arr) {
        int length = arr.length;

        for(int i = 0; i < length; i++) {
            // 第一种写法
//            for(int j = i; j > 0; j--) {
//                if(arr[j - 1].compareTo(arr[j]) > 0) {
//                    swap(arr, j - 1, j);
//                }else {
//                    break;
//                }
//            }
            // 第二种写法
            for(int j = i; j > 0 && arr[j - 1].compareTo(arr[j]) > 0; j--){
                swap(arr, j - 1, j);
            }
        }



    }

    public static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }


}
